package leetcode_100;

/**
 *@author 周杨
 *WildcardMatching_44
 *Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
 *
 *describe:假设我们用两个指针分别指向s和p字符串中要匹配的位置，首先分析下通配符匹配过程中会有哪些情况是成功：

s的字符和p的字符相等

p中的字符是?，这时无论s的字符是什么都可以匹配一个

p中遇到了一个*，这时无论s的字符是什么都没关系

之前的都不符合，但是p在之前的位置有一个*，我们可以从上一个*后面开始匹配

s已经匹配完，但是p后面还有很多连续的`*

这里1和2的情况比较好处理，关键在于如何处理3和4的情况。
当我们遇到一个*时，因为之后可能要退回至该位置重新匹配，我们要将它的下标记录下来，比如idxstar。
但是，当我们连续遇到两次4的情况，如何保证我还是能继续匹配s，而不是每次都退回idxstar+1导致循环呢？
所以我们还要记录一个idxmatch，用来记录用上一个*连续匹配到的s中的下标。最后，对于情况5，我们用一个循环跳过末尾的*跳过就行了。
 *2018年5月5日 下午2:41:27
 */
public class WildcardMatching_44 {
	String s;
	String p;
	
	public static void main(String[] args) {
		WildcardMatching_44 t=new WildcardMatching_44();
		System.out.println(t.isMatch1("aa", "a"));
		System.out.println(t.isMatch1("aa", "*"));
		System.out.println(t.isMatch1("cb", "?a"));
		System.out.println(t.isMatch1("adceb", "*a*b"));
		System.out.println(t.isMatch1("acdcb", "a*c?b"));
		
		System.out.println(t.isMatch1("", "*"));
		System.out.println(t.isMatch1("a", "a*"));
		System.out.println(t.isMatch1("ho", "ho**"));
		
		System.out.println(t.isMatch1("aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba", "a*******b"));
		
		System.out.println(t.isMatch1("bbbaaabaababbabbbaabababbbabababaabbaababbbabbbabb", "*b**b***baba***aaa*b***"));
		
		
		
		

	}
	public  boolean isMatch(String s, String p) {
        this.s=s;
        this.p=p;
        if(s.length()>0&&p.length()>0)
		if(s.charAt(s.length()-1)!=p.charAt(p.length()-1)&&p.charAt(p.length()-1)!='?'&&p.charAt(p.length()-1)!='*')
			return false;
		return help(0,0);
    }
	
	/**
	 * describe:非递归回溯方法 时间复杂度O(N)
	 * 2018年5月5日 下午2:29:34
	 */
	public boolean isMatch1(String s,String p) {
		//idxstar最近一个*的位置 idxmatch
		int idxs = 0, idxp = 0, idxstar = -1, idxmatch = 0;
        while(idxs < s.length()){
            // 当两个指针指向完全相同的字符时，或者p中遇到的是?时
            if(idxp < p.length() && (s.charAt(idxs) == p.charAt(idxp) || p.charAt(idxp) == '?')){
                idxp++;
                idxs++;
            // 如果字符不同也没有?，但在p中遇到是*时，我们记录下*的位置，但不改变s的指针
            } else if(idxp < p.length() && p.charAt(idxp)=='*'){
                idxstar = idxp;
                idxp++;
                //遇到*后，我们用idxmatch来记录*匹配到的s字符串的位置，和不用*匹配到的s字符串位置相区分
                idxmatch = idxs;
            // 如果字符不同也没有?，p指向的也不是*，但之前已经遇到*的话，我们可以从idxmatch继续匹配任意字符
            } else if(idxstar != -1){//有上一个*
                // 用上一个*来匹配，那我们p的指针也应该退回至上一个*的后面
                idxp = idxstar + 1;
                // 用*匹配到的位置递增
                idxmatch++;
                // s的指针退回至用*匹配到位置
                idxs = idxmatch;
            } else {
                return false;
            }
        }
        // 因为1个*能匹配无限序列，如果p末尾有多个*，我们都要跳过
        while(idxp < p.length() && p.charAt(idxp) == '*'){
            idxp++;
        }
        // 如果p匹配完了，说明匹配成功
        return idxp == p.length();
	}
	
	public boolean help(int index1,int index2) {
		if(index1==this.s.length()) {//如果第一个已经验证完毕
			if(index2==this.p.length())
				return true;
			for(int i=index2;i<this.p.length();++i) {//是否后面还有*
				if(this.p.charAt(i)!='*')
					return false;
			}
			return true;
		}
		if(index2==this.p.length())
			return false;
		if(s.charAt(index1)==p.charAt(index2)||p.charAt(index2)=='?')
			return help(index1+1,index2+1);
		if(p.charAt(index2)=='*') {
			boolean res=false ;
			for(int i=0;i<=s.length()-index1;++i) {
				res=help(index1+i,index2+1);
				if(res==true)
					return true;
			}
		}
		return false;		
	}

}
